# 分糖果(好题)

"""题目
两种糖果分别有9个和16个, 要全部分给7个小朋友, 每个小朋友得到的糖果总数最少为2个最多为5个, 问有多少种不同的分法. 糖果必须全部分完.
只要有其中一个小朋友在两种方案中得到的糖果不完全相同, 这两种方案就算作不同的方案.
"""


def candy(n, c0, c1):
    res = 0

    def dfs(depth, remain0, remain1, path: list[tuple]):
        nonlocal res
        if depth == n:  # 当深度为n也就是第n个孩子也已经分完, 不管是否糖果有没有剩余都直接结束该层递归
            if remain0 == 0 and remain1 == 0:  # 糖果数量没有剩余
                res += 1
            return

        # 剪枝1: 如果剩余糖果已经不够分给后面的小朋友
        if (n - depth) * 2 > remain0 + remain1:
            return
        # 剪枝2: 如果剩余的糖果已经分不完了
        if (n - depth) * 5 < remain0 + remain1:
            return

        for i in range(remain0 + 1):  # 分第一种糖果
            for j in range(remain1 + 1):  # 分第二种糖果
                if 2 <= i + j <= 5:
                    path.append((i, j))
                    dfs(depth + 1, remain0 - i, remain1 - j, path)

    dfs(0, c0, c1, [])
    return res


if __name__ == '__main__':
    print(candy(7, 9, 16))  # 5067671
